package leetcode.weekly.week298;

import leetcode.helper.H;

//Solution4Test
public class Solution4 {

	// Solution4Test
	public long sellingWood(int m, int n, int[][] prices) {
		int r = prices.length, c = prices[0].length;
		Long[][] dp = new Long[m + 1][n + 1];
		int[][] values = new int[m + 1][n + 1];
		// 类似hash的变换，方便查询，mn很小，prices的这种方式hash不会出问题
		for (int i = 0; i < prices.length; i++) {
			values[prices[i][0]][prices[i][1]] = prices[i][2];
		}
		// 小于他中的最大的
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				values[i][j] = Math.max(Math.max(values[i][j], values[i - 1][j - 1]),
						Math.max(values[i][j - 1], values[i - 1][j]));
			}
		}
		return this.selling(m, n, dp, values);
	}

	private long selling(int m, int n, Long[][] dp, int[][] values) {
		if (dp[m][n] != null) {
			return dp[m][n];
		}
		long ans1 = -1;
		for (int i = 1; i < m; i++) {
			// 横切最大
			ans1 = Math.max(this.selling(i, n, dp, values) + this.selling(m - i, n, dp, values), ans1);
		}
		long ans2 = -1;
		for (int i = 1; i < n; i++) {
			// 纵切最大
			ans2 = Math.max(this.selling(m, i, dp, values) + this.selling(m, n - i, dp, values), ans2);
		}
//		long ans3 = -1;
		long ans3 = values[m][n];
		long ans = Math.max(Math.max(ans1, ans2), ans3);
		dp[m][n] = ans;
		return ans;
	}

}
